<?php
/**
 * User: LRZ
 * Date: 2020/2/27
 * Time: 12:22
 */

$array = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0, 4];
heapSort($array);
print_r($array);
die;

function heapSort(&$array)
{
    /*
     *  堆排序实现过程
     *    1. 把无序数组构建成二叉堆。需要升序，则构建成最大堆；需要降序，则构建成最小堆
     *    2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶
     */

    // 把无序数组构建成最大堆
    buildHeap($array);
    // 循环删除堆顶元素，移动到集合尾部，调整堆产生新的堆顶
    for ($i = count($array) - 1; $i > 0; $i--) {
        // 最后一个元素和第一个元素互换
        $tmp       = $array[$i];
        $array[$i] = $array[0];
        $array[0]  = $tmp;
        // 下沉调整，生成新堆顶
        downAdjust($array, 0, $i);
    }
}

/**
 * 上浮调整
 * @param $array
 * @param int $upIndex
 */
function upAdjust(&$array, $upIndex = -1)
{
    $count = count($array);
    // 默认插入到末尾
    $childIndex  = $upIndex === -1 ? $count - 1 : $upIndex;
    $parentIndex = (int)(($childIndex - 1) / 2); // 父节点下标
    $tmp         = $array[$childIndex]; // tmp保存插入的叶子节点值，用于最后赋值
    while ($childIndex > 0 && $tmp < $array[$parentIndex]) {
        // 无需真正交换，单向赋值即可
        $array[$childIndex] = $array[$parentIndex];
        $childIndex         = $parentIndex;
        $parentIndex        = (int)(($parentIndex - 1) / 2);
    }
    $array[$childIndex] = $tmp;
}

/**
 * 下沉调整
 * @param $array
 * @param $parentIndex
 * @param $length
 */
function downAdjust(&$array, $parentIndex, $length)
{
    // tmp保存父节点值，用于最后的复制
    $tmp        = $array[$parentIndex];
    $childIndex = $parentIndex * 2 + 1;
    while ($childIndex < $length) {
        // 如果有右孩子，切右孩子大于（大于则是最大堆，小于则是最小堆）左孩子的值，则定位到右孩子
        if ($childIndex + 1 < $length && $array[$childIndex + 1] > $array[$childIndex]) {
            $childIndex++;
        }
        // 如果父节点大于（大于则是最大堆，小于则是最小堆）任何一个孩子的值、则直接退出
        if ($tmp >= $array[$childIndex]) {
            break;
        }
        // 无需真正交换，单向赋值即可
        $array[$parentIndex] = $array[$childIndex];
        $parentIndex         = $childIndex;
        $childIndex          = $childIndex * 2 + 1;
    }
    $array[$parentIndex] = $tmp;
}

/**
 * 构建二叉堆
 * @param $array
 */
function buildHeap(&$array)
{
    // 从最后一个非叶子节点开始，依次做下沉调整
    for ($i = (int)((count($array) - 2) / 2); $i >= 0; $i--) {
        downAdjust($array, $i, count($array));
    }
}